/**
 * 
 */
package com.google.code.jam;

import java.util.Scanner;

/**
 * @author sa
 *
 */
public class RotateService
{
	ParsingService parsingService;
	OutputService outputService;
	
	public void process(String inputFileName,String outFileName) throws Exception
	{
		parsingService=new ParsingService(inputFileName);
		outputService=new OutputService(outFileName);
		
		String records=parsingService.nextLine();
		int totRecs=Integer.parseInt(records);
		
		for(int i=1;i<=totRecs;i++)
		{
			String nk=parsingService.nextLine();
			Scanner scn=new Scanner(nk);
			int n=scn.nextInt();
			int k=scn.nextInt();
			solve(n,k);
		}

		outputService.writeResultInFile(outFileName);
	}
	
	private void solve(int n,int k)
	{
		
		//Prepare board
		int [][] board= new int[n][n];
		
		for(int i=0;i<n;i++)
		{
			String lineRec=parsingService.nextLine();
			for(int j=0;j<n;j++)
			{
				if(lineRec.charAt(j)=='.')
					board[i][j]=0;
				else if(lineRec.charAt(j)=='R')
					board[i][j]=1;
				else if(lineRec.charAt(j)=='B')
					board[i][j]=2;
			}
		}
		System.out.println("Board Ready:\n");
		print(board,n);
		
		int [][]rotated=rotateBoard(board,n);
		
		System.out.println("\nAfter Rotation:\n");
		print(rotated,n);
		
		applyGravity(rotated,n);
		System.out.println("\nAfter Gravity:\n");
		print(rotated,n);
		
		checkWin(rotated,n,k);
		
	}
	
	private void checkWin(int [][]gravited, int n, int k)
	{
		int RED=1;
		int BLUE=2;
		
		boolean redWin= horizantalChk(gravited,n,k,RED);
		boolean blueWin=horizantalChk(gravited,n,k,BLUE);
		
		
		
		System.out.println("Required K ="+k);
		System.out.println("horizontal redWin="+redWin);
		System.out.println("horizontal blueWin="+blueWin);
		
		if(!redWin)
			redWin= verticalChk(gravited,n,k,RED);
		
		if(!blueWin)
			blueWin=verticalChk(gravited,n,k,BLUE);
		

		System.out.println("verticalChk redWin="+redWin);
		System.out.println("verticalChk blueWin="+blueWin);
		
		if(!redWin)
			redWin= diagonalChk(gravited,n,k,RED);
		
		if(!blueWin)
			blueWin=diagonalChk(gravited,n,k,BLUE);
		

		System.out.println("diagonalChk redWin="+redWin);
		System.out.println("diagonalChk blueWin="+blueWin);
		
		outputService.insertCaseResult(redWin, blueWin);
		
	}
	
	private boolean diagonalChk(int[][] gravited, int n, int K, int t) {
		int count = 0;
		boolean win = false;

		outer: 
		for (int k = 0; k < n - 1; k++) 
		{
			int r = 0;
			int c = k;
			while (r < n  && c < n ) 
			{
				count = 0;
				while (r < n && c< n && gravited[r][c] == t) 
				{
					count++;
					r++;
					c++;
					if (count == K) 
					{
						win = true;
						break outer;
					}

				}

				while (r < n && c<n && gravited[r][c] != t)
				{
					r++;
					c++;
				}
				
				

			}
			
			r = k+1;
			c = 0;
			while (r < n && c < n ) 
			{
				count = 0;
				while (r < n && c< n && gravited[r][c] == t) 
				{
					count++;
					r++;
					c++;
					if (count == K) 
					{
						win = true;
						break outer;
					}

				}

				while (r < n && c<n && gravited[r][c] != t)
				{
					r++;
					c++;
				}
				
				

			}

		}

		return win;
	}
	
	
	private boolean verticalChk(int [][]gravited, int n, int k,int t)
	{
		int count=0;
		boolean win=false;
		
		outer: 
			for(int c=0;c<n;c++)
			{
				int r=0;
				while(r<n-1)
				{
					count=0;
					while( r<n && gravited[r][c]==t)
					{
						count++;
						r++;
						if(count==k)
						{
							win=true;
							break outer;
						}
							
					}
					
					while(r<n && gravited[r][c]!=t)
						r++;
				}
			}
		return win;
	}
	
	
	
	private boolean horizantalChk(int [][]gravited, int n, int k,int t)
	{
		int count=0;
		boolean win=false;
		
		outer: 
			for(int row=0;row<n;row++)
			{
				int col=0;
				while(col<n-1)
				{
					count=0;
					while(col<n && gravited[row][col]==t)
					{
						count++;
						col++;
						if(count==k)
						{
							win=true;
							break outer;
						}
							
					}
					
					while(col<n && gravited[row][col]!=t)
						col++;
				}
			}
		return win;
	}
	
	
	
	private void applyGravity(int [][]rotated, int n)
	{
		
		for(int col=0;col<n;col++)
		{
			int zeroel=n-1;
			while(zeroel>0)
			{
				while(rotated[zeroel][col]!=0 && zeroel > 0)
					zeroel--;
				
				int nonZeroEl=zeroel;
				
				while(rotated[nonZeroEl][col]==0 && nonZeroEl > 0)
					nonZeroEl--;
				
				if(rotated[zeroel][col]==0)
				{
					rotated[zeroel][col]=rotated[nonZeroEl][col];
					rotated[nonZeroEl][col]=0;
				}
				
				zeroel--;
			}
	
		}
		
		
	}
	
//	0 0 0 0 0 0
//	0 0 0 0 0 0
//	0 0 0 0 0 0
//	0 0 0 0 0 0
//	0 0 0 0 0 0
	
	
	private int[][] rotateBoard(int [][]board, int n)
	{
		int [][] rotated=new int[n][n];
		
		for(int i=n-1;i>=0;i--)
		{
			for(int j=0;j<n;j++)
				rotated[j][(n-1)-i]=board[i][j];
			
		}
		
		return rotated;
	}
	
	
	private void print(int [][]a, int n)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				System.out.print(a[i][j]+" ");
			
			System.out.println("\n");

		}
			
	}
}
